package leetcode;

import java.util.Arrays;

public class SearchInRotatedArray {

	//test case
	public static void main(String[] args) {
		SearchInRotatedArray ss = new SearchInRotatedArray();
		int[] nums = {2,3,6,0,1};
//		System.out.println(ss.search(nums, 7));
		System.out.println(ss.getBoundary(nums, 0, 4));
	}
	
	public int search(int[] nums, int target) {
        if(nums == null || nums.length <= 0){
            return 0;
        }
        //首先需要找到分界点
        //如果恰好旋转回到了原使状态
        int boundary = 0;	//boundary指向最小的元素下标
        if(nums[0] <  nums[nums.length - 1] || nums.length == 1){
            return binarySearch(nums, 0, nums.length - 1, target);
        }else{
            boundary = getBoundary(nums, 0, nums.length - 1, nums[0]);
        }
        
        //重构排好序的数组
//        System.out.println(boundary);
        int[] left = Arrays.copyOfRange(nums, 0, boundary);
//        for (int i = 0; i < left.length; i++) {
//			System.out.print(left[i] + " ");
//		}
//        System.out.println();
//        System.out.println("right array is: ");
        int[] right = Arrays.copyOfRange(nums, boundary, nums.length);
//        for (int i = 0; i < right.length; i++) {
//			System.out.print(right[i] + " ");
//		}
//        System.out.println();
        int index = -1;
        if( (index = binarySearch(left, 0, left.length - 1, target)) != -1){
        	return index;
        }else{
        	index = binarySearch(right, 0, right.length - 1, target);
        }
        return index == -1 ? index : index + left.length;
    }
	
	
	//获取“断点”，断点就是排好序时的最小的元素
    public int getBoundary(int[] nums, int left, int right, int leftVal){
    	if(left == right){
    		return nums[left] >= leftVal ? left + 1 : left;
    	}
    	//left小于right代表是排好序的
        if(nums[left] < nums[right]){
            return left;
        }
        int middle = left + (right - left) / 2;
        int index = -1;
        if(nums[middle] > leftVal){
        	index = getBoundary(nums, middle, right , leftVal);
        }else {
        	//这里之所以不写middle - 1，是因为middle可能就是最小的
        	index = getBoundary(nums, left, middle, leftVal);
        }
        return index;
    }
    
    //获取“断点”，断点就是排好序时的最小的元素
    public int getBoundary(int[] nums, int left, int right){
    	if(left == right){
    		return left;
    	}
    	//left元素的值小于right代表是排好序的
        if(nums[left] < nums[right]){
            return left;
        }
        int middle = left + (right - left) / 2;
        int index = -1;
        System.out.println(middle + " middle");
        if(nums[middle] > nums[right]){
        	index = getBoundary(nums, middle, right);
        }else if(nums[left] > nums[middle]){
        	//这里之所以不写middle - 1，是因为middle可能就是最小的
        	index = getBoundary(nums, left, middle);
        }
        return index;
    }
    
    
    public int binarySearch(int[] nums, int left, int right, int target){
//    	System.out.println("left : " + left + " right: " + right);
        if(left > right){
            return -1;  //如果没有找到，返回-1
        }
        int middle = left + (right - left) / 2;
        int index = -1;
        if(nums[middle] == target){
            return middle;
        }else if(nums[middle] <= target){
            index = binarySearch(nums, middle + 1, right, target);
        }else{
            index = binarySearch(nums, left, middle - 1, target);
        }
        return index;
    }
}
